package tree;
import java.util.*;

import org.junit.Test;
public class Ex437 {
    class Solution1 {
        //Node转码为id数字做存储，配合sum做动态规划
        int[][] f;
        public int pathSum(TreeNode root, int targetSum) {
            //进行后序遍历，对每个节点编号，记录进id对照表，并记录节点的数值总和【null一律视为id == 0】
            Map<TreeNode, Integer> map = new HashMap<>();   
            int sum = 0, idx = 1, min = Integer.MIN_VALUE;
            map.put(null, 0);
            Stack<TreeNode> stack = new Stack<>();
            TreeNode cur = root, last = null;
            //非递归方式后序遍历二叉树
            while (cur != null || !stack.isEmpty()) {
                while (cur != null) {
                    stack.push(cur);
                    cur = cur.left;
                }
                cur = stack.peek();
                if (cur.right != null && last != cur.right) {
                    cur = cur.right;
                } else {
                    cur = stack.pop();
                    sum += cur.val;
                    map.put(cur, idx++);
                    last = cur;
                    cur = null;
                }
            }
            //初始化动态数组
            this.f = new int[idx][sum + 1];
            //进行动态规划填表
            fill(root, map, 0, targetSum);
            return f[map.get(root)][targetSum];
        }

        public void fill(TreeNode root, Map<TreeNode, Integer> map, int cur, int target) {
            if (root == null) {
                //检查当前是否满足和
                f[0][cur] += cur == target ? 1 : 0; //0指空节点
                return;
            }
            if (cur == target) {
                //将当前节点放入表格
                f[map.get(root)][cur] += 1;
                return;
            }
            //动态规划需要自底向上，首先来到最底层
            fill(root.left, map, cur, target);
            fill(root.right, map, cur, target);
            int sum = cur + root.val, left = map.get(root.left), right = map.get(root.right);
            //可以要之前的存的，也可以不要
            f[map.get(root)][cur] = f[left][sum] + f[right][sum] + f[left][root.val] + f[right][root.val];
        }
    }

    @Test
    public void test() {
        Solution1 s = new Solution1();
        TreeNode root = TreeUtils.createTree(new Integer[]{10,5,-3,3,2,null,11,3,-2,null,1});
        int targetSum = 8;
        System.out.println(s.pathSum(root, targetSum));
    }

    class Solution {
        int[][] f;
        int unpossible;
        public int pathSum(TreeNode root, int targetSum) {
            //进行后序遍历，对每个节点编号，记录进id对照表，并记录节点的数值总和【null一律视为id == 0】
            Map<TreeNode, Integer> map = new HashMap<>();   
            int sum = 0, idx = 1;
            map.put(null, 0);
            Stack<TreeNode> stack = new Stack<>();
            TreeNode cur = root, last = null;
            //非递归方式后序遍历二叉树
            while (cur != null || !stack.isEmpty()) {
                while (cur != null) {
                    stack.push(cur);
                    cur = cur.left;
                }
                cur = stack.peek();
                if (cur.right != null && last != cur.right) {
                    cur = cur.right;
                } else {
                    cur = stack.pop();
                    sum += cur.val;
                    map.put(cur, idx++);
                    last = cur;
                    cur = null;
                }
            }
            this.f = new int[idx][sum + 1];
            this.unpossible = sum + 1;
            for (int i = 0; i < idx; i++) {
                Arrays.fill(f[i], sum + 1); //设置为不可能存在的值
            }
            return dfs(map, root, 0, targetSum);
        }

        public int dfs(Map<TreeNode, Integer> map, TreeNode root, int cur, int target) {
            if (root == null) {
                return cur == target ? 1 : 0;
            }
            int idx = map.get(root);
            if (f[idx][cur] != unpossible) return f[idx][cur];
            if (cur == target) {
                f[idx][cur] += 1;
            }
            int sum = cur + root.val;
            int res = dfs(map, root.left, root.val, target) + dfs(map, root.right, root.val, target) +
            dfs(map, root.left, sum, target) + dfs(map, root.right, sum, target);
            f[idx][cur] += sum;
            return res;
        }
    }

    class Solution2 {
        //前缀和 + 回溯
        /* 
            前缀和：从根节点到当前节点的路径上的总和 curSum
            前缀和字典：将一条路径上的前缀和与其数量放入字典，方便查找是否存在这样的前缀和 curSumMap
            假设遍历到某个节点cur，当前前缀和为curSum, 所要求得的路径和为target
            因此，若是我能在**当前路径**上的前面某个节点node得到一个前缀和为 sum - target, 那么从node到达cur的路径和就为target = sum - (sum - target)

            路径和map为了保证是当前节点研途的路径，需要在回溯时将当前节点造成的影响还原
        */

          //前缀和 + 回溯
        /* 
            前缀和：从根节点到当前节点的路径上的总和 curSum
            前缀和字典：将一条路径上的前缀和与其数量放入字典，方便查找是否存在这样的前缀和 curSumMap
            假设遍历到某个节点cur，当前前缀和为curSum, 所要求得的路径和为target
            因此，若是我能在**当前路径**上的前面某个节点node得到一个前缀和为 sum - target, 那么从node到达cur的路径和就为target = sum - (sum - target)

            路径和map为了保证是当前节点研途的路径，需要在回溯时将当前节点造成的影响还原
        */
        public int pathSum1(TreeNode root, int targetSum) {
            if (root == null) return 0;
            if (root.left == null && root.right == null) return root.val == targetSum ? 1 : 0;
            Map<Integer, Integer> curSumMap = new HashMap<>();
            curSumMap.put(0, 1); //路径和为0的路径有不走这一条
            return getPathNum(root, 0, targetSum, curSumMap);
        }
        public int getPathNum(TreeNode cur, int curSum, int target, Map<Integer, Integer> curSumMap) {
            if (cur == null) return 0;
            curSum += cur.val;
            int res = 0;
            res += curSumMap.getOrDefault(curSum  - target, 0);//查看是否存在这样的路径
            //当前路径和数量加一
            curSumMap.put(curSum, curSumMap.getOrDefault(curSum, 0) + 1);
            res += (getPathNum(cur.left, curSum, target, curSumMap) + getPathNum(cur.right, curSum, target, curSumMap));
            //消除当前路径当前节点对map的影响
            curSumMap.put(curSum, curSumMap.get(curSum) - 1);
            return res;
        }
        //先序遍历，以每个节点作为根节点，查看是否能使得sum为0
        public int pathSum(TreeNode root, int targetSum) {
            //主方法进行先序遍历
            if (root == null) return 0;
            //将root作为根节点，查看是否能够找到某一时刻为0的节点，在以左右子树为根节点，进行累计
            return dfs(root, targetSum) + pathSum(root.left, targetSum) + pathSum(root.right, targetSum);
        }

        public int dfs(TreeNode root, int sum) {
            if (root == null) return 0;
            sum -= root.val;
            return (sum == 0 ? 1 : 0) + dfs(root.left, sum) + dfs(root.right, sum);
        }
    }

    @Test
    public void test1() {
        Solution2 s = new Solution2();
        TreeNode root = TreeUtils.createTree(new Integer[]{10,5,-3,3,2,null,11,3,-2,null,1});
        int targetSum = 8;
        System.out.println(s.pathSum(root, targetSum));
    }
}
